/*
Date:20210517 10:16AM
key:1.再二叉树堂兄弟那题收到了启发，通过输入一个节点指针查看节点深度，注意不能是值，因为值会重复。
    第一次层序就按层序遍历放入节点指针。再通过树深度创建大数组，再遍历层序指针数组，将指针放入对应深度的数组。
 */
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        if(root==nullptr){return 0;}
        else
        {
            return max(maxDepth(root->left),maxDepth(root->right))+1;
        }
    }
    //递归版本
    int deep1(TreeNode* root,TreeNode* &root1,int&dep)
    {
        if(root==nullptr){return 0;}
        if(root==root1)
        {
            
            return dep;
        }
        else
        {
            dep++;
            int a=deep1(root->left,root1,dep);
            dep--;

            dep++;
            int b=deep1(root->right,root1,dep);
            dep--;
            return max(a,b);
        }
    }
    int deep2(TreeNode* &root,TreeNode* &root1)
    {
        int dep=0;
        return deep1(root,root1,dep);
    }
    vector<TreeNode*> levelOrder1(TreeNode* root)
    {
        queue<TreeNode*>v;
        vector<TreeNode*>V;
        if(root==nullptr){return V;}
        else
        {
            v.push(root);
            while(!v.empty())
            {
                if(v.front()->left!=nullptr)
                {
v.push(v.front()->left);
                }
                                if(v.front()->right!=nullptr)
                {
v.push(v.front()->right);
                }

                V.push_back(v.front());
                v.pop();
            }

        }
        return V;
    }
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>>re;
        re.resize(maxDepth(root));
        vector<TreeNode*> v=levelOrder1(root);
        for(TreeNode*&i:v)
        {
            //cout<<i<<" ";
            re[deep2(root,i)].push_back(i->val);
        }
        return re;
    }
};